package top.hkyzf.study.leetcode.tree;

import org.junit.Test;

/**
 * description: 
 * @author zhufeng
 * @date 2023/4/18 9:30
 * @version V1.0
 */
public class 节点与其祖先之间的最大差值_1026 {

    @Test
    public void testMaxAxcestorDiff () {
        TreeNode left3 = new TreeNode(13);
        TreeNode right3 = new TreeNode(14, left3, null);
        TreeNode left2 = new TreeNode(4);
        TreeNode right2 = new TreeNode(7);
        TreeNode left1 = new TreeNode(1);
        TreeNode right1 = new TreeNode(6, left2, right2);
        TreeNode left = new TreeNode(3, left1, right1);
        TreeNode right = new TreeNode(10, null, right3);
        TreeNode root = new TreeNode(8, left, right);
        int i = maxAncestorDiff(root);
        System.out.println(i);
    }

    private int ans = 0;

    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }

    /**
     * 深度优先
     */
    private int dfs(TreeNode node, int max, int min) {
        if (node != null) {
            max = Math.max(max, node.val);
            min = Math.min(min, node.val);
            dfs(node.left, max, min);
            dfs(node.right, max, min);
        }
        ans = Math.max(ans, max - min);
        return ans;
    }

}
